/**
 * @file review.cc
 * @author snow-tyan (zziywang@163.com)
 * @brief {Life is too short to learn cpp.}
 * @version 0.1
 * @date 2022-02-28
 *
 * @copyright Copyright (c) 2022
 *
 */

// 二分：704. 35. 34. 69. 367. 153. 154.
// 双指：27. 26. 283. 977. 844.
// 滑窗：209. 904. 76. （窗口哈希法，哈希的是窗口）
// 模拟：59. 54.

#include <iostream>
#include <string>
#include <unordered_map>
#include <vector>
using std::cout;
using std::endl;
using std::string;
using std::unordered_map;
using std::vector;

template <class T>
void print(const T &t)
{
    class T::const_iterator it = t.begin();
    for (; it != t.end(); ++it) {
        cout << *it << " ";
    }
    cout << endl;
}

class Solution
{
  public:
    // 704.
    int search(vector<int> &nums, int target)
    {
        int left = 0, right = nums.size() - 1;
        // // 左闭右闭区间
        // while (left <= right){
        //     int middle = left + (right - left) / 2;
        //     if (nums[middle] == target){
        //         return middle;
        //     }else if (nums[middle] < target){
        //         left = middle + 1;
        //     }else {
        //         right = middle - 1;
        //     }
        // }
        // 左闭右开区间
        while (left < right) {
            int middle = left + (right - left) / 2;
            if (nums[middle] == target) {
                return middle;
            } else if (nums[middle] < target) {
                left = middle + 1;
            } else {
                right = middle;
            }
        }
        return -1;
    }
    // 35.
    int searchInsert(vector<int> &nums, int target)
    {
        int left = 0, right = nums.size() - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) {
                return mid;
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        // 不存在，此时left == right + 1
        return left;
    }
    // 34.
    vector<int> searchRange(vector<int> &nums, int target)
    {
        int leftIdx = searchInsert(nums, target);
        int rightIdx = searchInsert(nums, target + 1) - 1;
        // not found (nums[leftidx]!=target但有可能越界)
        if (leftIdx == nums.size() || nums[leftIdx] != target) {
            return {-1, -1};
        }
        return {leftIdx, rightIdx};
    }
    // 69.
    int mySqrt(int x)
    {
        if (x == 0 || x == 1) {
            return x;
        }
        int left = 1, right = x / 2;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if ((long long)mid * mid == x) {
                return mid;
            } else if ((long long)mid * mid < x) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        // left > right
        return right;
    }
    // 367.
    bool isPerfectSquare(int num)
    {
        if (num == 1) {
            return true;
        }
        int left = 1, right = num / 2;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if ((long long)mid * mid == num) {
                return true;
            } else if ((long long)mid * mid < num) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return false;
    }
    // 153.
    // 最小值左右侧均是单调递增区间，且左侧元素》右侧元素
    // 可通过与最右边值比较从而确定最小值位于哪个半区间
    int findMin(const vector<int> &nums)
    {
        int left = 0, right = nums.size() - 1;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] < nums[right]) { // 说明已经越过最小值
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        // left == right
        return nums[left];
    }
    // 154.
    int findMin154(const vector<int> &nums)
    {
        int left = 0, right = nums.size() - 1;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] < nums[right]) {
                right = mid;
            } else if (nums[mid] > nums[right]) {
                left = mid + 1;
            } else { // nums[mid]==nums[right]
                --right;
            }
        }
        return nums[left];
    }
    // 27.
    int removeElement(vector<int> &nums, int val)
    {
        int i = 0, j = 0, n = nums.size();
        while (j < n) {
            if (nums[j] == val) {
                ++j;
                continue;
            }
            nums[i++] == nums[j++];
        }
        return i;
    }
    // 26.
    int removeDuplicates(vector<int> &nums)
    {
        int i = 0, j = 1, n = nums.size();
        if (n == 0) {
            return 0;
        }
        while (j < n) {
            if (nums[i] == nums[j]) {
                ++j;
                continue;
            }
            nums[++i] = nums[j++];
        }
        return i + 1;
    }
    // 283.
    void moveZeroes(vector<int> &nums)
    {
        int i = 0, j = 0, n = nums.size();
        while (j < n) {
            if (nums[j] != 0) {
                std::swap(nums[i], nums[j]);
                ++i;
            }
            ++j;
        }
    }
    // 977.二次函数
    // 双指巧妙
    vector<int> sortedSquares(const vector<int> &nums)
    {
        int n = nums.size();
        vector<int> ret(n, 0);
        int i = 0, j = n - 1, k = n - 1;
        while (i <= j) {
            if (nums[i] * nums[i] > nums[j] * nums[j]) {
                ret[k--] = nums[i] * nums[i];
                ++i;
            } else {
                ret[k--] = nums[j] * nums[j];
                --j;
            }
        }
        return ret;
    }
    // 844.
    bool backspaceCompare(string s, string t)
    {
        int i = s.length() - 1, j = t.length() - 1;
        int cnti = 0, cntj = 0;
        while (i >= 0 || j >= 0) {
            while (i >= 0) {
                if (s[i] == '#') {
                    ++cnti;
                    --i;
                } else if (cnti > 0) {
                    --cnti;
                    --i;
                } else {
                    break;
                }
            }
            while (j >= 0) {
                if (t[j] == '#') {
                    ++cntj;
                    --j;
                } else if (cntj > 0) {
                    --cntj;
                    --j;
                } else {
                    break;
                }
            }

            if (i >= 0 && j >= 0) { // ij均合法
                if (s[i] != t[j]) {
                    return false;
                }
            } else {                    // 至少已经有一个走到头了
                if (i >= 0 || j >= 0) { // 此时若还有一个没走到头，必为false
                    return false;
                }
            }
            --i;
            --j;
        }
        return true;
    }
    // 209. 和为target的最短子数组
    int minSubArrayLen(int target, vector<int> &nums)
    {
        int i = 0, j = 0, n = nums.size();
        int minLen = n + 1;
        int winSum = 0; // 正整数数组 窗口和
        while (j < n) {
            winSum += nums[j++];
            while (winSum >= target) {
                // len = j - i + 1, 但是前面j已经++过了
                minLen = std::min(minLen, j - i);
                winSum -= nums[i++];
            }
        }
        return minLen == n + 1 ? 0 : minLen;
    }
    // 904. 哈希+滑窗
    int totalFruit(const vector<int> &fruits)
    {
        unordered_map<int, int> map; // 维护水果的类型数
        int i = 0, n = fruits.size();
        int fruitsCount = 0; // 收集水果的最大数目
        for (int j = 0; j < n; ++j) {
            ++map[fruits[j]];
            while (map.size() > 2) { // 超过2元素，窗口左端点移动
                --map[fruits[i]];
                if (map[fruits[i]] == 0) {
                    map.erase(fruits[i]);
                }
                ++i;
            }
            fruitsCount = std::max(fruitsCount, j - i + 1);
        }
        return fruitsCount;
    }
    // 76. s中涵盖t所有字符的最小子串
    // 双哈希+滑窗 (哈希“窗口”和字符串t)
    string minWindow(string s, string t)
    {
        if (s.length() < t.length()) {
            return "";
        }
        unordered_map<char, int> mapWin; // 窗口
        unordered_map<char, int> mapT;   // 字符串t
        int i = 0, n = s.length();
        int match = 0; // 已匹配字符数
        string ret;    // 含t的子串
        for (char &ch : t) {
            ++mapT[ch];
        }
        for (int j = 0; j < n; ++j) {
            auto it = mapT.find(s[j]); // t中出现的字符，若未在t中出现，不予理会
            if (it != mapT.end()) {
                ++mapWin[s[j]];
                if (mapWin[s[j]] == mapT[s[j]]) {
                    ++match; // 某字符数相等，匹配+1
                }
            }
            // 匹配完成，寻找最小子串
            while (match == mapT.size()) {
                if (j - i + 1 < ret.length() || ret.empty()) {
                    ret = s.substr(i, j - i + 1);
                }
                auto it = mapWin.find(s[i]);
                if (it != mapWin.end()) {
                    --mapWin[s[i]];
                    if (mapWin[s[i]] < mapT[s[i]]) {
                        --match;
                    }
                    if (mapWin[s[i]] == 0) {
                        mapWin.erase(s[i]);
                    }
                }
                ++i;
            }
        }
        return ret;
    }
    // 59.螺旋矩阵：正方形
    vector<vector<int>> generateMatrix(int n)
    {
        vector<vector<int>> mat(n, vector<int>(n, 0));
        int l = 0, r = n - 1, u = 0, d = n - 1;
        int num = 1;
        while (num <= n * n) { // 可解决n为奇数时的情况
            for (int i = l; i <= r; ++i) {
                mat[u][i] = num++;
            }
            ++u; // 从左往右填充完，上边界下缩
            for (int i = u; i <= d; ++i) {
                mat[i][r] = num++;
            }
            --r; // 从上到下填充完，右边界左缩
            for (int i = r; i >= l; --i) {
                mat[d][i] = num++;
            }
            --d; // 从右往左填充完，下边界上缩
            for (int i = d; i >= u; --i) {
                mat[i][l] = num++;
            }
            ++l; // 从下到上填充完，左边界右缩
        }
        return mat;
    }
    // 54.螺旋矩阵，矩形
    vector<int> spiralOrder(vector<vector<int>> &matrix)
    {
        int m = matrix.size(), n = matrix[0].size();
        vector<int> ret(m * n, 0);
        int l = 0, r = n - 1, u = 0, d = m - 1;
        int k = 0;
        while (true) {
            for (int i = l; i <= r; ++i) {
                ret[k++] = matrix[u][i];
            }
            if (++u > d)
                break;
            for (int i = u; i <= d; ++i) {
                ret[k++] = matrix[i][r];
            }
            if (--r < l)
                break;
            for (int i = r; i >= l; --i) {
                ret[k++] = matrix[d][i];
            }
            if (--d < u)
                break;
            for (int i = d; i >= u; --i) {
                ret[k++] = matrix[i][l];
            }
            if (++l > r)
                break;
        }
        return ret;
    }
};

Solution solve = Solution();

void test704()
{
    vector<int> nums = {-1, 0, 3, 5, 9, 12};
    cout << solve.search(nums, 2) << endl  //-1
         << solve.search(nums, 0) << endl  // 1
         << solve.search(nums, 9) << endl; // 4
}

void test69()
{
    cout << solve.mySqrt(2) << endl
         << solve.mySqrt(4) << endl
         << solve.mySqrt(8) << endl
         << solve.mySqrt(16) << endl
         << solve.mySqrt(65536) << endl;
}

void test367()
{
    cout << solve.isPerfectSquare(16) << endl
         << solve.isPerfectSquare(14) << endl
         << solve.isPerfectSquare(65536) << endl
         << solve.isPerfectSquare(65537) << endl;
}

void test153()
{
    cout << solve.findMin({3, 4, 5, 1, 2}) << endl
         << solve.findMin({2, 3, 4, 5, 1}) << endl
         << solve.findMin({4, 5, 6, 7, 0, 1, 2}) << endl
         << solve.findMin({11, 13, 15, 17}) << endl;
}

void test154()
{
    cout << solve.findMin154({3, 4, 5, 1, 2}) << endl
         << solve.findMin154({2, 2, 2, 3, 4, 5}) << endl
         << solve.findMin154({2, 2, 2, 3, 4, 5, 1, 1, 1, 1, 1, 1}) << endl;
}

void test977()
{
    print(solve.sortedSquares({-4, -1, 0, 3, 10}));
    print(solve.sortedSquares({-7, -3, 2, 3, 11}));
}

void test904()
{
    cout << solve.totalFruit({1, 2, 1}) << endl
         << solve.totalFruit({0, 1, 2, 2}) << endl
         << solve.totalFruit({1, 2, 3, 2, 2}) << endl
         << solve.totalFruit({3, 3, 3, 1, 2, 1, 1, 2, 3, 3, 4}) << endl;
}

void test59()
{
    auto ret = solve.generateMatrix(3);
    for (auto &r : ret) {
        print(r);
    }
    ret = solve.generateMatrix(4);
    for (auto &r : ret) {
        print(r);
    }
}

void test54()
{
    vector<vector<int>> matrix1 = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}};
    vector<vector<int>> matrix2 = {{1, 2, 3, 4}, {5, 6, 7, 8}, {9, 10, 11, 12}};
    print(solve.spiralOrder(matrix1));
    print(solve.spiralOrder(matrix2));
}

int main()
{
    // test704();
    // test69();
    // test367();
    // test153();
    // test154();
    // test977();
    // test904();
    // test59();
    test54();
    return 0;
}